In multi-agent systems, agents form relationships among themselves according to their own internal preferences and decision-making logic. In general, there is no “dictator” function that determines the inter-relationships between agents. This level of self-organization is one of the defining features of multi-agent systems, and one of the most valuable.
Nevertheless, it is often desirable that the topology of the web of inter-agent relationships exhibit certain globally-defined properties. This is especially true if the multi-agent system is under the nominal administration of a single entity, such as a corporation, or was configured to solve some cooperative problem. For example, so-called “random” networks, such as the network of physical internet routers, in which the degree-distribution of nodes roughly follows a bell-curve, are relatively robust against targeted attacks on nodes, because the ill effects of the failure of any one node is approximately the same for all nodes. On the other hand, “scale-free” networks, in which the degree-distribution of nodes follows a power law, are relatively robust against random node failure, because most nodes are relatively unimportant to the overall network's functioning. Reference in this regard can be made to Albert, R., Jeong, H., and Barabasi, A.-L., “Error and attack tolerance in complex networks”, Nature 406:378-381 (2000).
For the purposes of this patent application, a “scale-free network” is any network of relationships in which the degree-distribution of the nodes is characterized by a power law. The “degree” of a node denotes the number of connections a given node has with other nodes, i.e., the number of relationships (or relationships of a given type) that a given node is in. Thus, for scale-free networks, the histogram of node-degrees has the feature that relatively fewer nodes are found to have relatively higher degrees, with the overall relationship following a power-law curve.
It is also typically the case that the overall desired network topology can change with time. For example, during typical functioning it is desirable for the system to maintain robustness against random failure; but in the event of a real or an expected attack, it would be even more desirable for the system to instead protect itself against the attack. For this to occur the system should exhibit an ability to continually adjust the statistical properties of the network topology.
A problem thus exists in the prior art as to how to dynamically and intelligently modify, or alter, or “tune” the topology of the network of relationships in an operating multi-agent system, in order to achieve a desired global behavior, such as robustness against attack or against random failure, without overly restricting the ability of agents to autonomously form and break relationships.
There is a body of established work on the relationship between network topology and system robustness, especially the tradeoff between robustness against attack versus robustness against random failure, as was noted above. In addition, however, there exists relevant work on the relationship between the degree of inter-connectivity among nodes in a localized neighborhood, and the rate at which chain reactions of failures are propagated. Reference in this regard can be made to Keeling, M., “The effects of local spatial structure on epidemiological invasions”, Proc. Roy. Soc. Lond. B 266, 859-869 (1999). This previous work indicates that changes to the topological structure of the network of relationships can have a profound effect on system dynamics, and in particular can result in improved system performance in the face of different kinds of failure or attack.
However, prior to this invention, there has been no description of a mechanism whereby these changes could be effected in the case of multi-agent systems.
There has also been extensive work on so-called “self-healing networks”, in which elements of a network (e.g., internet or telecommunications routers) respond to failures of nodes by reconfiguring themselves in a distributed fashion. These approaches are sometimes proactive, in the sense that they attempt to prepare the system to optimally respond to failures in advance of the failure actually occurring. Reference in this regard can be made to U.S. Pat. No. 6,061,735: “Network restoration plan regeneration responsive to network topology changes”, by James D. Rogers. However, this prior work does not address the need for systems to dynamically tune a preferred system topology to protect against different kinds of attack or failure, as the need arises.